package 力扣91;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName : Day_16_513_找树左下角的值
 * @Author : 骆发茂
 * @Date: 2021/12/27 11:47
 * @Description : https://leetcode-cn.com/problems/find-bottom-left-tree-value/
 * https://leetcode-cn.com/problems/find-bottom-left-tree-value/solution/513-zhao-shu-zuo-xia-jiao-de-zhi-bfs-dfs-aawe/
 */
public class Day_16_513_找树左下角的值_bfs {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    /**
     * 思路一：BFS
     * 用队列存储节点，先进先出
     * 从右往左遍历，也就是在往队列中添加数据时，先添加右子节点，再添加左子节点
     * 当队列为空时，循环结束，最后一个遍历到的节点就是最左边的节点
     * 返回最左边节点的值
     *
     * 作者：edelweisskoko
     * 链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value/solution/513-zhao-shu-zuo-xia-jiao-de-zhi-bfs-dfs-aawe/
        */
    class Solution {
        public int findBottomLeftValue(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);//从二叉树中获取节点，放到队列中，offer/add
            TreeNode node = null;
            //当队列为空时，循环结束，最后一个遍历到的节点就是最左边的节点
            while (!queue.isEmpty()) {

                //之后就是队列中添加子节点，从右往左，node就是一直变化，从右往左遍历放在node
                //遍历完node，也就是队列中已经是空的了，最后一个放在node 的就是树左下角。
                node = queue.poll(); //从队列的头中取出，放到node中,取队首元素并删除

                /*接下来就是一直左右左右遍历，先添加右子节点，再添加左子节点*/
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left != null) {
                    queue.offer(node.left);

                }

            }
            //返回最左边节点的值
            return node.val;
        }
    }
}